/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年05月04日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if( root == NULL )
            return NULL;

        TreeNode *p = root;
        TreeNode *parent = root;
        while( p ){
            if( key < p->val ){
                parent = p;
                p = p->left;
            }else if( key > p->val ){
                parent = p;
                p = p->right;
            }else{
                break;
            }
        }
        if(p == NULL)
            return root;

        TreeNode* childNode = keepBST(p);
        if(p == root)
            return childNode;

        if(p == parent->left){
            parent->left = childNode;
        }else{
            parent->right = childNode;
        }

        return root;
    }

private:
    TreeNode* keepBST(TreeNode *root){
        if(root->left == NULL)
            return root->right;
        if(root->right == NULL)
            return root->left;

        TreeNode *p = root->left;
        while(p->right){
            p = p->right;
        }

        p->right = root->right;

        return root->left;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
  		if(root == NULL)
			return NULL;

        if( key == root->val ){
			return keepBST(root);
        }else if( key < root->val ){
            root->left = deleteNode(root->left, key);
        }else{
            root->right = deleteNode(root->right, key);
        }
        
        return root;
    }

private:
    TreeNode* keepBST(TreeNode *root){
        if(root->left == NULL)
            return root->right;
        if(root->right == NULL)
            return root->left;

        TreeNode *p = root->left;
        while(p->right){
            p = p->right;
        }

        p->right = root->right;

        return root->left;
    }

};
